In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W Bajtocji odbędzie się Parada Kolorowych Pociągów. Na torach technicznych bajtockiego dworca trwają intensywne przygotowania. Na dworcu jest równoległych torów, ponumerowanych od do . Na -tym torze ustawiono pociąg o numerze . Każdy pociąg składa się z wagonów, z których każdy jest pomalowany na jeden z 26 kolorów (oznaczonych małymi literami alfabetu angielskiego). Mówimy, że dwa pociągi wyglądają identycznie, jeśli ich kolejne wagony są tego samego koloru.
Parada będzie polegać na tym, że co minutę stacyjny dźwig zamieni miejscami pewną parę wagonów. Prawdziwa parada odbędzie się jednak dopiero jutro. Dziś dyżurny ruchu Bajtazar bacznie przyglądał się próbie generalnej. Dokładnie zapisał sobie ciąg kolejno zamienianych par wagonów.
Bajtazar nie lubi, gdy zbyt wiele pociągów wygląda identycznie. Chciałby, żebyś dla każdego pociągu policzył maksymalną liczbę pociągów, które w pewnym momencie wyglądają identycznie jak pociąg w owym momencie.
Napisz program, który:
Pierwszy wiersz wejścia zawiera trzy liczby naturalne , oraz (, , ), oznaczające odpowiednio liczbę pociągów, ich długość oraz liczbę wykonywanych zamian wagonów. W kolejnych wierszach znajdują się opisy kolejnych pociągów stojących na torach. -ty z tych wierszy składa się z małych liter alfabetu angielskiego reprezentujących kolory kolejnych wagonów -tego pociągu. Za opisami pociągów znajduje się wierszy zawierających opisy kolejnych zamian, w kolejności ich wykonywania. W -tym z tych wierszy znajdują się cztery liczby całkowite , , , (, , lub ) i opisują one -tą operację wykonywaną przez dźwig - zamianę wagonu numer z pociągu z wagonem pociągu .
Twój program powinien wypisać dokładnie wierszy. -ty wiersz powinien zawierać jedną liczbę całkowitą - liczbę pociągów wyglądających tak samo jak pociąg numer w pewnym momencie czasu.
Dla danych wejściowych:
5 6 7 ababbd abbbbd aaabad caabbd cabaad 2 3 5 4 5 3 5 5 3 5 2 2 1 2 4 3 2 2 5 1 1 1 3 3 4 1 5 6
poprawną odpowiedzią jest:
3 3 3 2 3
Oto wygląd pociągów w kolejnych fazach próby generalnej:
tor 1: ababbd ababbd ababbd ababbd aaabbd aaabbd aaabbd aaabbd tor 2: abbbbd ababbd ababbd aaabbd aaabbd acabbd acabbd acabbd tor 3: aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd tor 4: caabbd caabbd caabbd caabbd cabbbd cabbbd cabbbd dabbbd tor 5: cabaad cabbad caabbd caabbd caabbd aaabbd aaabbd aaabbc (0) (1) (2) (3) (4) (5) (6) (7)
Dla pociągów 1, 2 i 3 najwięcej podobnych było np. w momencie (4) (były one nawzajem do siebie podobne). Dla pociągu 5 najwięcej mu podobnych było w momentach (5) i (6). Dla pociągu 4 najwięcej podobnych było np. w momencie (2).
Autor zadania: Piotr Stańczyk.